This invention relates to rules-based software systems.
One approach to the design of artificial intelligence systems has been to use a rules-based approach. In rules-based systems, a set of rules (or “productions”) defines the behavior of the system. Rules are selected based on specifications of the rules and the state of information that is known to the system about a particular problem. Selected rules are applied. Application of the rules in general changes the state of information, thereby potentially allowing further rules to be selected. Generally, rules-based systems in which information is repeatedly added to the state of information, thereby allowing further rules to be applied until a desired result is achieved or until there are no remaining applicable rules, are referred to as “forward-chaining” rules-based systems.
One well-known rules-based system is the OPS5 system, which was developed at Carnegie Mellon University in the early 1980's and later commercialized by a number of companies. In OPS5, the state of information is represented as a set of facts (or “working memory elements,” “WMEs”). Facts belong to identified classes, and each fact (an instance of a class) assigns values to a number (zero or more) attributes for that class. In general, a fact takes the form “(identifier ^attribute1 value1 ^attribute2 value2 . . . )” where “identifier” is the name of a class, and “attribute1, “attribute2”, etc. are names of attributes for that class. An example of a fact could be “(person ^height 6.0 ^weight 210)” for a person (an instance of a class named person) whose height is 6.0 feet and weight is 210 pounds.
Each rule (production) has the form “LHS condition - - - >RHS action”, where the left-hand-side (LHS) condition on the state of information under which the rule is applicable and the right-hand-side (RHS) action specifies the operations to perform when applying the rule. This condition is a Boolean expression that combines a number of terms with logical operators. The logical operators are AND and ANDNOT, and each of the terms is referred to as a condition element. Each condition element is a logical function of the value or values of specified attributes for an identifier, for example, the attribute having a particular value or belonging to a specified set of values, not having a particular value, not belonging to a specified set, etc. A condition element is represented as “(identifier ^attribute value)” if the identifier/attribute must have the specified value, and as “(identifier ^attribute<<value1 value2 . . . >>)” if the identifier/attribute must belong to the specified set of values. A condition element can be a logical function or a combination of multiple attributes. For example such a combination can be represented as “(person ^weight>200 ^height<6.0)” to indicate that the weight attribute must be greater than 200 and the height attribute less than 6.0. A condition element is evaluated to be true for a fact if that fact includes attribute/value pairs that together determine that the overall logical function is true. Each condition element of a rule can match a different fact, and a rule's condition is true if the logical combination of the condition elements is true for a particular set of facts. Some systems such as OPS5 allow the values in condition elements to be variables that must be bound to the same value in each of the condition elements of a rule's condition that together match a particular rule.
An action of a rule can include one or more separate actions, each of which can modify the state of information, for example, by adding a fact with particular attributes, or by removing or modifying an existing fact. Execution proceeds in a loop where first one or more applicable rules are identified along with the facts that make them applicable, then one of these rules is selected, and then the action of that selected rule is performed.
The task of identifying applicable rules and the facts that make them applicable can be quite computationally expensive. One particular algorithm that is used in many implementations of forward-chaining rules-based systems, such as OPS5, is the Rete algorithm, originally developed by C. L. Forgy. The Rete algorithm uses a data flow network to represent the conditions of the rules. The network has two parts, one part performs the tests required to evaluate the individual condition elements, and a second part combines the condition elements to form the overall conditions for the rules. The outputs of the first part (and the input to the second part) are a set of memories each associated with a different condition element for holding the set of facts that satisfy (or may satisfy for some values of the variables) that condition element. The second part includes storage elements associated with different combinations of condition elements, each identifying the possible corresponding combinations of facts that satisfy that combination of condition elements. Some of these storage elements are associated with overall conditions that particular rule must satisfy, and the presence of any combination of facts in these storage elements indicate that the corresponding rules are applicable given those facts.